//== SAGITTARIUS ============================================================================

//== BEGINNING OF CODE ===============================================================

#include "sagittarius/core/SagittariusCore.h"

//SAGITTARIUS headers:
#include "sagittarius/unicode/CUnicode.h"
#include "sagittarius/re/reParser.h"

#include <stdio.h>
//#include <time.h>
#include <malloc.h>
//#include <string.h>

LOOKUP_VAL_TYPE lookup[LOOKUP_N];

/*UnicodeCChar nextTok(const UnicodeCChar* w) {
    SAGITTARIUS_ASSERT(*w != UC_Null);
    return *(++w);
}*/

//#define PRINT_EXPANSIONS

#ifdef PRINT_EXPANSIONS
    #define USING_EXPANSION(x) printf(x); printUnicodeBuf(state->w); printf("\n");
#else
    #define USING_EXPANSION(x)
#endif

#define DISTRIBUTE_NEGATIVE

//-- Stream processing --

int match(parserState* state, const UnicodeCChar c) {
    SAGITTARIUS_ASSERT(*state->w != UC_Null);
    SAGITTARIUS_ASSERT(*state->w == c);
    if(*state->w == c) {
        state->x = *(++state->w);
        return 1;
    } else {
        return 0;
    }
}

UnicodeCChar consume(parserState* state) {
    SAGITTARIUS_ASSERT(*state->w != UC_Null && "Consumed end of buffer");
    UnicodeCChar tmp = state->x;
    state->x = *(++state->w);
    /*{
        UnicodeCChar a[2];
        a[0] = tmp;
        a[1] = UC_Null;
        printf("Consumed ");
        printUnicodeBuf(a);
        printf("\n");
    }*/
    return tmp;
}

int isControlTok(const UnicodeCChar x) {
    switch (x) {
        case (unsigned int)0x7C:
            return 1;
            break;
        case CONST_RE_LPAREN:
            return 1;
            break;
        case CONST_RE_RPAREN:
            return 1;
            break;
        default:
            return 0;
    }
}

///nodeIsBinop
int nodeIsBinop(expNode* n) {
    switch(n->type) {
        case AST_NODE_TYPE_CONCAT:
            return 1;
        case AST_NODE_TYPE_UNION:
            return 1;
        case AST_NODE_TYPE_INTERSECTION:
            return 1;
        default:
            return 0;
    }
}

///distributeComplement
/*int distributeComplement(expNode* n) {
    if(!n->inv)
        AN(0 && "No negative to distribute");
        return 1; //no negative to distribute
    if(nodeIsBinop(n)) {
        AN(n->n1 && "Must have child to distribute negative");
        n->n1->inv = 1;
        AN(n->n2 && "Must have child to distribute negative");
        n->n2->inv = 1;
        n->inv = 0;
    } else {
        //distribution affects binary operations only
        return 0;
    }
}*/

///distributeComplement recursive
void distributeComplementR(expNode* n) {
    //does not complain when there is no negative to distribute
    if(n->inv) {
        switch(n->type) {
            case AST_NODE_TYPE_CONCAT:
                //AN(0);
                //I do not think there is a way to make this
                //work without adding another binary operation
                //to RE. Details in notes.
                return;
            case AST_NODE_TYPE_UNION:
                //DeMorgan
                AN(n->n1 && "Must have child to distribute negative");
                n->n1->inv = 1;
                distributeComplementR(n->n1);
                AN(n->n2 && "Must have child to distribute negative");
                n->n2->inv = 1;
                distributeComplementR(n->n2);
                n->inv = 0;
                n->type = AST_NODE_TYPE_INTERSECTION;
                return;
            case AST_NODE_TYPE_INTERSECTION:
                //DeMorgan
                AN(n->n1 && "Must have child to distribute negative");
                n->n1->inv = 1;
                distributeComplementR(n->n1);
                AN(n->n2 && "Must have child to distribute negative");
                n->n2->inv = 1;
                distributeComplementR(n->n2);
                n->inv = 0;
                n->type = AST_NODE_TYPE_UNION;
                return;
            default:
            //distribution affects binary operations only
            return;
        }
    } else {
        if(n->n1) distributeComplementR(n->n1);
        if(n->n2) distributeComplementR(n->n2);
    }
}

/// re_createParserState
parserState re_createParserState(const UnicodeCChar* w) {
    parserState r;
    r.w = w;
    r.x = *w;
    SAGITTARIUS_ASSERT(r.x && "Begins with null char");
    return r;
}

//-- Expression parsers --

/// re_parseExpE
expNode* re_parseExpE(parserState* state) {
    //E must expand E -> |TE'
    USING_EXPANSION("E -> OE'\n");
    expNode* o = re_parseExpO(state);
    expNode* ep = re_parseExpEp(state);
    if(ep) {
        expNode* int_node = re_createNode();
        int_node->type = AST_NODE_TYPE_INTERSECTION;
        int_node->n1 = o;
        int_node->n2 = ep;
        #ifdef REPARSER_COMPUTE_NULLABLE
            int_node->nullable = int_node->n1->nullable && int_node->n2->nullable;
        #endif
        return int_node;
    } else {
        return o;
    }
}

expNode* re_parseExpEp(parserState* state) {
    if(state->x == CONST_RE_AMP) {
        consume(state);
        //use expansion E'-> |TE'
        USING_EXPANSION("E' -> &TE'\n");
        expNode* o = re_parseExpO(state);
        expNode* ep = re_parseExpEp(state);
        if(ep) {
            expNode* int_node = re_createNode();
            int_node->type = AST_NODE_TYPE_INTERSECTION;
            int_node->n1 = o;
            int_node->n2 = ep;
            #ifdef REPARSER_COMPUTE_NULLABLE
                int_node->nullable = int_node->n1->nullable && int_node->n2->nullable;
            #endif
            return int_node;
        } else {
            return o;
        }
    } else {
        //use expansion E' -> ep
        return NULL;
    }
}

expNode* re_parseExpO(parserState* state) {
    //O must expand: O -> TO'
    USING_EXPANSION("O -> TO'\n");
    expNode* t = re_parseExpT(state);
    expNode* op = re_parseExpOp(state);
    if(op) {
        expNode* union_node = re_createNode();
        union_node->type = AST_NODE_TYPE_UNION;
        union_node->n1 = t;
        union_node->n2 = op;
        #ifdef REPARSER_COMPUTE_NULLABLE
            union_node->nullable = union_node->n1->nullable || union_node->n2->nullable;
        #endif
        return union_node;
    } else {
        return t;
    }
}

expNode* re_parseExpOp(parserState* state) {
    if(state->x == CONST_RE_VBAR) {
        consume(state);
        //use expansion E'->|TE'
        USING_EXPANSION("E' -> |TE'\n");
        expNode* t = re_parseExpT(state);
        expNode* op = re_parseExpOp(state);
        if(op) {
            expNode* union_node = re_createNode();
            union_node->type = AST_NODE_TYPE_UNION;
            union_node->n1 = t;
            union_node->n2 = op;
            #ifdef REPARSER_COMPUTE_NULLABLE
                union_node->nullable = union_node->n1->nullable || union_node->n2->nullable;
            #endif
            return union_node;
        } else {
            return t;
        }
    } else {
        //use expansion E' -> ep
        return NULL;
    }
}

expNode* re_parseExpT(parserState* state) {
    //T must expand: T -> FT'
    USING_EXPANSION("T -> FT'\n");
    expNode* f = re_parseExpF(state);
    expNode* tp = re_parseExpTp(state);
    if(tp) {
        expNode* concat_node = re_createNode();
        concat_node->type = AST_NODE_TYPE_CONCAT;
        concat_node->n1 = f;
        concat_node->n2 = tp;
        #ifdef REPARSER_COMPUTE_NULLABLE
            concat_node->nullable = concat_node->n1->nullable && concat_node->n2->nullable;
        #endif
        return concat_node;
    } else {
        return f;
    }
}

expNode* re_parseExpTp(parserState* state) {
    //determine if char is in FIRST(T')
    if( state->x != CONST_RE_VBAR && state->x != CONST_RE_AMP && 
        state->x != CONST_RE_LPAREN && state->x != CONST_RE_RPAREN &&
        state->x != UC_Null) {
        //expand T' -> FT'
        USING_EXPANSION("T' -> FT'\n");
        expNode* f = re_parseExpF(state);
        expNode* tp = re_parseExpTp(state);
        if(tp) {
            expNode* concat_node = re_createNode();
            concat_node->type = AST_NODE_TYPE_CONCAT;
            concat_node->n1 = f;
            concat_node->n2 = tp;
            #ifdef REPARSER_COMPUTE_NULLABLE
                concat_node->nullable = concat_node->n1->nullable && concat_node->n2->nullable;
            #endif
            return concat_node;
        } else {
            return f;
        }
    } else {
        //expand T' -> ep
        return NULL; //empty
    }
}

expNode* re_parseExpF(parserState* state) {
    //match negation, if available
    int do_inv = 0;
    if(state->x == CONST_RE_CARROT) {
        do_inv = 1;
        consume(state); //'^'
    }
    
    if(state->x == CONST_RE_LPAREN) {
        //use expansion F -> (E)
        USING_EXPANSION("F -> (E)\n");
        consume(state); //'('
        expNode* e = re_parseExpE(state);
        match(state, CONST_RE_RPAREN);
        e->inv = do_inv; //apply negation if appropriate
        #ifdef REPARSER_COMPUTE_NULLABLE
            if(e->inv) e->nullable = !e->nullable;
        #endif
        #ifndef DISTRIBUTE_COMPLEMENT
            //AN(distributeComplement(e));
        #endif
        //match closure, if available
        if(state->x == CONST_RE_STAR) {
            e->closed = 1;
            consume(state); //'*'
            #ifdef REPARSER_COMPUTE_NULLABLE
                e->nullable = 1;
            #endif
        }
        return e;
    } else {
        if(state->x == UC_Null) {
            SAGITTARIUS_ASSERT(0 && "Reached end of buffer expecting primitive");
            return NULL;
        }
        //use expansion F -> sym
        expNode* e = re_parseExpPrimitive(state);
        e->inv = do_inv; //apply negation if appropriate
        #ifdef REPARSER_COMPUTE_NULLABLE
            if(e->inv) e->nullable = !e->nullable;
        #endif
        //match closure, if available
        if(state->x == CONST_RE_STAR) {
            e->closed = 1;
            consume(state); //'*'
            #ifdef REPARSER_COMPUTE_NULLABLE
                e->nullable = 1;
            #endif
        }
        return e;
    }
}

/// re_parseExpPrimitive
expNode* re_parseExpPrimitive(parserState* state) {
    expNode* n = re_createNode();
    SAGITTARIUS_ASSERT(n);
    n->type = AST_NODE_TYPE_PRIMITIVE;
    
    UnicodeCChar c = consume(state);
    AT(!isControlTok(c), "Found stray control token"); //used to pass c && "Found stray control token" to isControlTok - DANGEROUS!
    n->cs = re_createCSSym(c);
    #ifdef REPARSER_COMPUTE_NULLABLE
        n->nullable = 0;
    #endif
    return n;
}

